Digital maps are commonly employed to depict real-world features on a computer display. Typically the digital map acts to display a window or similar area representing a geographic coverage area upon which representations of geographic features that exist in the corresponding real-world geographic area may be mapped and depicted. Also typically a database representing mappable geographic features, such as for example roads, buildings, or points of interest, is maintained as a source of geographic location and other information that may be referenced as necessary for purposes such as selecting items to be mapped and determining their location and appearance on the map. (For the purpose of this discussion, the terms “feature” and “item” are used interchangeably to refer to entities that may be depicted on the digital map).
The depiction of real-world features on such a map or other 2- or 3-dimensional representation poses the problem of identifying specific features of interest among the possibly many other features depicted or eligible for depiction. For example, if a digital map depicts retail shops that exist within a geographic area, the user may be interested in identifying shops that sell a specific type of product. Because information about specific products carried might not be represented in the visual representation of each shop, it is likely to be necessary for the computer program that composes the digital map to access database information in order to identify shops that match this criteria, and then depict them in a different manner from the others, perhaps by highlighting or by application of a symbol such as a pushpin symbol, so that the user may distinguish them from other depicted features that do not match the criteria.
A number of methods are practiced in the prior art for the purpose of identifying and differentially depicting sought items. For example, several well known internet-based mapping services (such as Mapquest, for example) begin by presenting a digital map that initially depicts only a few important features such as roads and major landmarks, and the user is expected to specify a search criterion, perhaps by typing a keyword or business category, thereby commanding the map to additionally display previously undepicted items that match the criterion. Alternatively, such as with maps provided by Yahoo!, Inc. and other providers, the user may be asked to check one or more checkboxes or other controls in order to specify that items of corresponding predetermined categories become visible, leaving items in other categories invisible. For example, a checkbox labeled “grocery stores” might cause grocery stores to become depicted if checked.
One shortcoming of maps that show items selectively as described above, that is, only in response to user specification of one or more search criteria, is that many items of potential interest to the user may fail to become depicted, and thereby remain unknown to the user, simply because the user has not thought to specify a search criterion that would reveal them. On the other hand, the alternative strategy of showing every mappable feature simultaneously would likely cause the map to be so cluttered as to make it difficult for the user to discern items of interest.
Another shortcoming comes to light in applications in which the digital map depicts features whose attributes change frequently. Because digital maps as seen in the prior art rely on deliberate user action to compose and issue a search command that in turn determines what is to be displayed, it is possible that a displayed set of search results may become invalid with the passage of time. Suppose for example that the database contains information representing local retail shops and also the current inventory of each shop; and that this inventory is frequently updated in response to deliveries and sales of goods at each store. If the user wishes to identify stores that currently have in stock a specific product, and one of the matching stores runs out of the product after the search has been conducted, the change in matching status of this store would not be known to the user until and unless the user reissues the search command and thereby causes the display to be refreshed. Therefore, the prior art continues to pose the problem of applying and displaying the results of a search of dynamically changing items in a way that maintains validity of displayed results without requiring the user to repeatedly issue a search command, or requiring constant automatic update of the display.
Further, the search criterion is typically applied to database records by traversing the records as stored in memory space or disk storage in an order representing their relative position in memory space or on disk (for example, in an alphabetical or numeric order). Because the database of mappable items may be very large (perhaps covering an entire state or country), it would be preferable that only the geographically relevant portion of the database, that is, only the records pertaining to features within the geographic region currently within or near the geographic area of the map display, be searched. To this end, it is obvious to anyone skilled in the art that each database item might first undergo a preliminary test for geographic location to determine that the item is geographically within the area of interest and therefore eligible for further application of the search criterion. However, even this initial test may prove computationally burdensome, especially if the search criterion is repeatedly and continuously applied in order to keep the displayed results accurate over time. It would be preferable that even this initial geographic test be eliminated and that only a relatively small subset of items already known to be geographically eligible should participate in a given application of the search criterion.